/**
 * 解数独
 *
 * 编写一个程序，通过填充空格来解决数独问题。
 * 数独的解法需 遵循如下规则：
 * 数字 1-9 在每一行只能出现一次。
 * 数字 1-9 在每一列只能出现一次。
 * 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
 * 数独部分空格内已填入了数字，空白格用 '.' 表示。
 *
 * 示例 1：
 * 输入：board = [
 * ["5","3",".",".","7",".",".",".","."],
 * ["6",".",".","1","9","5",".",".","."],
 * [".","9","8",".",".",".",".","6","."],
 * ["8",".",".",".","6",".",".",".","3"],
 * ["4",".",".","8",".","3",".",".","1"],
 * ["7",".",".",".","2",".",".",".","6"],
 * [".","6",".",".",".",".","2","8","."],
 * [".",".",".","4","1","9",".",".","5"],
 * [".",".",".",".","8",".",".","7","9"]]
 * 输出：[
 * ["5","3","4","6","7","8","9","1","2"],
 * ["6","7","2","1","9","5","3","4","8"],
 * ["1","9","8","3","4","2","5","6","7"],
 * ["8","5","9","7","6","1","4","2","3"],
 * ["4","2","6","8","5","3","7","9","1"],
 * ["7","1","3","9","2","4","8","5","6"],
 * ["9","6","1","5","3","7","2","8","4"],
 * ["2","8","7","4","1","9","6","3","5"],
 * ["3","4","5","2","8","6","1","7","9"]]
 * 解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
 *
 * 提示：
 * board.length == 9
 * board[i].length == 9
 * board[i][j] 是一位数字或者 '.'
 * 题目数据 保证 输入数独仅有一个解
 */

/**
 * 这题我们可以观察到, 一个地方有很多种可能性的值, 然后后面的值也会
 * 跟着前面的值而改变, 这很明显就是让我们使用深搜和回溯了
 * 时间复杂度 : O(n^(n^2))
 * 空间复杂度 : O(n^2)
 */


public class Main {


    // 测试用例
    public static void main(String[] args) {
        Main test = new Main();
//        char[][] board = new char[][]{
//                {'.', '.', '.', '.'},
//                {'3', '.', '.', '.'},
//                {'.', '.', '4', '.'},
//                {'.', '2', '3', '.'}
//        };
        char[][] board = new char[][]{
                {'.','.','9','7','4','8','.','.','.'},
                {'7','.','.','.','.','.','.','.','.'},
                {'.','2','.','1','.','9','.','.','.'},
                {'.','.','7','.','.','.','2','4','.'},
                {'.','6','4','.','1','.','5','9','.'},
                {'.','9','8','.','.','.','3','.','.'},
                {'.','.','.','8','.','3','.','2','.'},
                {'.','.','.','.','.','.','.','.','6'},
                {'.','.','.','2','7','5','9','.','.'}
        };
        test.solveSudoku(board);
    }

    // ***************************************
    // LeetCode上运行会错误(也不知道啥原因, 但是是可以判成功的) (这里用了全局变量)

//    static int n = 9;
//    static int m = 3;
//    static boolean isComp = false;
//    static boolean[][] col;
//    static boolean[][] row;
//    static boolean[][][] sp;
//
//    public boolean solveSudoku(char[][] board) {
//
//        col = new boolean[n][n];
//        row = new boolean[n][n];
//        sp = new boolean[m][m][n];
//
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < n; j++) {
//                if (board[i][j] != '.') {
//                    int in = board[i][j] - '0' - 1;
//                    col[i][in] = true;
//                    row[j][in] = true;
//                    sp[i / m][j / m][in] = true;
//                }
//            }
//        }
//
//        dfs(0, 0, board);
//
//        return isComp;
//    }
//
//    private void dfs (int i, int j, char[][] board) {
//
//        // 寻找下一个为空的位置
//        while (board[i][j] != '.') {
//            if (++j == n) {
//                j = 0;
//                i++;
//            }
//            if (i == n) {
//                isComp = true;
//                return;
//            }
//        }
//
//        for (int x = 1; x <= n; x++) {
//            if (col[i][x - 1] || row[j][x - 1] || sp[i / m][j / m][x - 1]) {
//                continue;
//            }
//            board[i][j] = (char)(x + '0');
//            col[i][x - 1] = true;
//            row[j][x - 1] = true;
//            sp[i / m][j / m][x - 1] = true;
//
//            dfs(i, j, board);
//
//            if (isComp) {
//                return;
//            }
//
//            board[i][j] = '.';
//            col[i][x - 1] = false;
//            row[j][x - 1] = false;
//            sp[i / m][j / m][x - 1] = false;
//        }
//    }

    // *******************************************
    // 这个版本没有用到全局变量, 而是有效就直接返回

    // 这里我们把题目中的定值给设置成 static 的, 这样方便我们可以改题目
    static int n = 9;
    static int m = 3;

    // 这里分别代表 每行每列和每个矩阵中的数字的出现
    static boolean[][] col;
    static boolean[][] row;
    static boolean[][][] sp;

    public boolean solveSudoku(char[][] board) {

        // 初始化
        col = new boolean[n][n];
        row = new boolean[n][n];
        sp = new boolean[m][m][n];

        // 将数字的出现记录下来
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] != '.') {

                    // 这里要减一, 因为我们的下标是 0 ~ 8, 而出现存的数是 1 ~ 9
                    int in = board[i][j] - '0' - 1;
                    col[i][in] = true;
                    row[j][in] = true;
                    sp[i / m][j / m][in] = true;
                }
            }
        }

        // 先从第一个数开始深搜
        return dfs(0, 0, board);
    }


    // 这里面要解决的问题核心是我们要列举第一个数的可能性, 因为是可解的, 所以我们在遍历完
    // 第一个的所有可能性的时候一定是得出结果的, 所以我们不用怕后面会找不到答案, 因为只要
    // 遍历完第一个数肯定就会找到答案, 列举完第一个数后就要将它记录下来, 并开始列举后面的
    // 数, 首先我们要找到需要列举的数, 并且我们要是成功的列举到最后一个位置了, 就已经成功
    // 了, 直接返回就可以了
    // 在列举这个数的所有可能性还没有进入下一个数的时候, 就是前面一个列举的数肯定出错了, 这
    // 时候我们就要回溯上去了, 注意要将原来的变为 '.', 因为我们的找寻需要列举的数就是靠这个
    // 来寻找的
    private boolean dfs (int i, int j, char[][] board) {

        // 寻找下一个为空的位置
        while (board[i][j] != '.') {
            // 要是 j到界了, 就向下走
            if (++j == n) {
                j = 0;
                i++;
            }

            // 要是 i越界了, 就说明已经列举完了
            if (i == n) {

                // 列举完就已经解出结果了
                return true;
            }
        }

        // 这里我们列举每一个数字
        for (int x = 1; x <= n; x++) {

            // 判断 行 列 矩阵 中有没有重复的
            if (col[i][x - 1] || row[j][x - 1] || sp[i / m][j / m][x - 1]) {
                continue;
            }

            // 这里要注意要转为 字符
            board[i][j] = (char)(x + '0');

            // 做上标记
            col[i][x - 1] = true;
            row[j][x - 1] = true;
            sp[i / 3][j / 3][x - 1] = true;

            // 深搜
            if (dfs(i, j, board)) {

                // 要是已经有效了, 就会一直沿着这里返回回去
                return true;
            }

            // 要是深搜出来了, 就说明这里的值是错的, 我们将它还原, 并抹除记录
            board[i][j] = '.';
            col[i][x - 1] = false;
            row[j][x - 1] = false;
            sp[i / m][j / m][x - 1] = false;
        }

        // 基本不会执行到这, 为了通过编译, 加的
        return false;
    }
}